{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete Columns to Make Sorted II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minDeletionSize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删列造序 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定由 <code>n</code> 个字符串组成的数组 <code>strs</code>，其中每个字符串长度相等。</p>\n",
    "\n",
    "<p>选取一个删除索引序列，对于 <code>strs</code> 中的每个字符串，删除对应每个索引处的字符。</p>\n",
    "\n",
    "<p>比如，有 <code>strs = [\"abcdef\", \"uvwxyz\"]</code>，删除索引序列 <code>{0, 2, 3}</code>，删除后 <code>strs</code> 为<code>[\"bef\", \"vyz\"]</code>。</p>\n",
    "\n",
    "<p>假设，我们选择了一组删除索引 <code>answer</code>，那么在执行删除操作之后，最终得到的数组的元素是按 <strong>字典序</strong>（<code>strs[0] <= strs[1] <= strs[2] ... <= strs[n - 1]</code>）排列的，然后请你返回 <code>answer.length</code> 的最小可能值。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [\"ca\",\"bb\",\"ac\"]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释： </strong>\n",
    "删除第一列后，strs = [\"a\", \"b\", \"c\"]。\n",
    "现在 strs 中元素是按字典排列的 (即，strs[0] <= strs[1] <= strs[2])。\n",
    "我们至少需要进行 1 次删除，因为最初 strs 不是按字典序排列的，所以答案是 1。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [\"xc\",\"yb\",\"za\"]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "strs 的列已经是按字典序排列了，所以我们不需要删除任何东西。\n",
    "注意 strs 的行不需要按字典序排列。\n",
    "也就是说，strs[0][0] <= strs[0][1] <= ... 不一定成立。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>strs = [\"zyx\",\"wvu\",\"tsr\"]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "我们必须删掉每一列。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == strs.length</code></li>\n",
    "\t<li><code>1 <= n <= 100</code></li>\n",
    "\t<li><code>1 <= strs[i].length <= 100</code></li>\n",
    "\t<li><code>strs[i]</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-columns-to-make-sorted-ii](https://leetcode.cn/problems/delete-columns-to-make-sorted-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-columns-to-make-sorted-ii](https://leetcode.cn/problems/delete-columns-to-make-sorted-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"ca\",\"bb\",\"ac\"]', '[\"xc\",\"yb\",\"za\"]', '[\"zyx\",\"wvu\",\"tsr\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, A: List[str]) -> int:\n",
    "        count = 0\n",
    "        # 记录的是满足条件的所有列的每一个元素的的严格大于情况.\n",
    "        cuts = [False] * (len(A) - 1)\n",
    "        for col in zip(*A):\n",
    "            # sign_1表示cuts是否全都为True\n",
    "            # sign_2表示当前列是否满足条件\n",
    "            sign_1 = sign_2 = True\n",
    "            for i in range(len(col)-1):\n",
    "                if not cuts[i]:\n",
    "                    sign_1 = False\n",
    "                if not cuts[i] and col[i] > col[i+1]:\n",
    "                    sign_2 = False\n",
    "                    break\n",
    "            # 如果cuts全都是严格大于,那么就可以返回结果了.\n",
    "            if sign_1:\n",
    "                break\n",
    "            # 如果当前列不满足条件,就需要删除,否则更新cuts\n",
    "            if sign_2:\n",
    "                for i in range(len(col)-1):\n",
    "                    if col[i] < col[i+1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n, m = len(strs), len(strs[0])\n",
    "        ans = 0\n",
    "\n",
    "        # 表示已判断出来字典序关系\n",
    "        increasing = [False] * n\n",
    "\n",
    "        for i in range(m):\n",
    "            flag = True\n",
    "            for j in range(1, n):\n",
    "                if not increasing[j] and strs[j][i] < strs[j-1][i]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if not flag:\n",
    "                ans += 1\n",
    "            else:\n",
    "                for j in range(1, n):\n",
    "                    if strs[j][i] > strs[j-1][i] and not increasing[j]:\n",
    "                        increasing[j] = True\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self, strs: List[str], index:int, del_lst:List[int]):\n",
    "        n = len(strs[0])\n",
    "        # print(strs,n)\n",
    "        for i in range(1,len(strs)):\n",
    "            left = 0\n",
    "            while left in del_lst or (left<n and strs[i][left]==strs[i-1][left]):\n",
    "                left+=1\n",
    "            # print(left,strs[i][left],strs[i-1][left])\n",
    "            if left<n and strs[i][left]<strs[i-1][left] and left==index:\n",
    "                return False\n",
    "        return True\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs[0])\n",
    "        ans = 0\n",
    "        del_lst = []\n",
    "        for i in range(n):\n",
    "            if self.check(strs,i,del_lst):\n",
    "                ans+=0\n",
    "            else:\n",
    "                del_lst.append(i)\n",
    "                ans+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        '''m,n=len(strs),len(strs[0])\n",
    "        flag=[0]*m #flag[i]=1表示strs[i]>strs[i-1]\n",
    "        cnt=0\n",
    "        for i in range(n):#判断是否删除第i个字母\n",
    "            tempflag=[0]*m\n",
    "            isdeleted=False\n",
    "            for j in range(1,m):\n",
    "                if flag[j]:\n",
    "                    tempflag[j]=1\n",
    "                    continue\n",
    "                if strs[j][i]<strs[j-1][i]:\n",
    "                    isdeleted=True\n",
    "                    break\n",
    "                elif strs[j][i]>strs[j-1][i]:\n",
    "                    tempflag[j]=1\n",
    "            if isdeleted:\n",
    "                cnt+=1\n",
    "            else:\n",
    "                flag=tempflag[::]\n",
    "        return cnt'''\n",
    "        '''n,m=len(strs),len(strs[0])\n",
    "        cnt=0\n",
    "        flag=[1]*(n-1)\n",
    "        for i in range(m):\n",
    "            if sum(flag)==0:break\n",
    "            temp=flag[::]\n",
    "            bool_=False\n",
    "            for j in range(n-1):\n",
    "                if temp[j]:\n",
    "                    if strs[j][i]<strs[j+1][i]:\n",
    "                        temp[j]=0\n",
    "                    elif strs[j][i]>strs[j+1][i]:\n",
    "                        bool_=True\n",
    "                        cnt+=1\n",
    "                        break\n",
    "            if not bool_:flag=temp[::]\n",
    "        return cnt'''\n",
    "        n,m=len(strs),len(strs[0])\n",
    "        ret,flag=0,[1]*(n-1)\n",
    "        for i in range(m):\n",
    "            if sum(flag)==0:break\n",
    "            temp=flag[::]\n",
    "            for j in range(n-1):\n",
    "                if flag[j]==0:continue\n",
    "                if strs[j][i]<strs[j+1][i]:\n",
    "                    flag[j]=0\n",
    "                elif strs[j][i]>strs[j+1][i]:\n",
    "                    ret+=1\n",
    "                    flag=temp[::]\n",
    "                    break\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "\n",
    "        def is_sorted(A):\n",
    "            return all(A[i] <= A[i + 1] for i in range(len(A) - 1))\n",
    "\n",
    "        ans = 0\n",
    "        cur = ['' for _ in range(len(strs))]  \n",
    "\n",
    "        for col in zip(*strs):\n",
    "            temp = cur[:]\n",
    "            for i, letter in enumerate(col):\n",
    "                temp[i] = temp[i] + letter\n",
    "\n",
    "            if is_sorted(temp):\n",
    "                cur = temp\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        ans = 0\n",
    "        n = len(strs)\n",
    "        m = len(strs[0])\n",
    "        flag = [False] * n\n",
    "\n",
    "        for i in range(m):\n",
    "            sorted_flag = True\n",
    "            for j in range(1, n):\n",
    "                # 前面非递增且j-1 到 递减，无序\n",
    "                if not flag[j] and strs[j][i] < strs[j-1][i]:\n",
    "                    sorted_flag = False\n",
    "                    break\n",
    "            if not sorted_flag:\n",
    "                ans += 1\n",
    "            else:\n",
    "                for j in range(1, n):\n",
    "                    if not flag[j] and strs[j][i] > strs[j-1][i]:\n",
    "                        flag[j] = True\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        cuts = [False] * (len(strs) - 1)\n",
    "        ans = 0\n",
    "        for col in zip(*strs):\n",
    "            if all(cuts[i] or col[i] <= col[i+1] for i in range(len(col)-1)):\n",
    "                for i in range(len(col)-1):\n",
    "                    # col[i] <= col[i+1]不可取是因为当出现 \"xga\",\"xfb\",\"yfa\"时候，需要保证xa, xb有序\n",
    "                    if col[i] < col[i+1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, A: List[str]) -> int:\n",
    "        count=0\n",
    "        record=[False]*(len(A)-1)\n",
    "        for col in zip(*A):\n",
    "            sign1=True\n",
    "            sign2=True\n",
    "            for i in range(len(A)-1):\n",
    "                if record[i]==False:\n",
    "                    sign1=False \n",
    "                    if col[i]>col[i+1]:\n",
    "                        sign2=False \n",
    "                        break\n",
    "            if sign1==True:\n",
    "                break \n",
    "            if sign2==True:\n",
    "                for i in range(len(A)-1):\n",
    "                    if col[i]<col[i+1]:\n",
    "                        record[i]=True\n",
    "                         \n",
    "            else:\n",
    "                count+=1\n",
    "            \n",
    "            \n",
    "        return count\n",
    "\n",
    "#如果大家都和平，直接count结束（sign1)\n",
    "#如果大家有没有不冲突（sign2），如果有冲突直接武力干涉（+1），如果只是可能存在不和平，\n",
    "#看看哪家没有和平（sign2）标false但是武力没有加1\n",
    "#最后知道都和平为止看看用了几次武力"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        res = 0\n",
    "        n = len(strs[0])\n",
    "        num = len(strs)\n",
    "        tmdnk=[ False for i in range(num-1)]\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            flag=0\n",
    "            for j in range(num-1):\n",
    "                if (not tmdnk[j]) and strs[j][i]>strs[j+1][i]:\n",
    "                    res+=1\n",
    "                    flag=1\n",
    "                    break\n",
    "            if flag==0:\n",
    "                for j in range(num-1):\n",
    "                    if strs[j][i]<strs[j+1][i]:\n",
    "                        tmdnk[j]=True\n",
    "            # print(tmdnk)\n",
    "        return res \n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        res = 0\n",
    "        n = len(strs[0])\n",
    "        num = len(strs)\n",
    "        tmdnk=[ False for i in range(num-1)]\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            flag=0\n",
    "            for j in range(num-1):\n",
    "                if (not tmdnk[j]) and strs[j][i]>strs[j+1][i]:\n",
    "                    res+=1\n",
    "                    flag=1\n",
    "                    break\n",
    "            if flag==0:\n",
    "                for j in range(num-1):\n",
    "                    if strs[j][i]<strs[j+1][i]:\n",
    "                        tmdnk[j]=True\n",
    "            # print(tmdnk)\n",
    "        return res \n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        def is_sorted(arr):\n",
    "            return all(arr[i] <= arr[i + 1] for i in range(len(arr) - 1))\n",
    "        res = 0\n",
    "        cur = [\"\" for _ in range(len(strs))]\n",
    "        for col in zip(*strs):\n",
    "            curr = cur[:]\n",
    "            for i in range(len(col)):\n",
    "                curr[i] += col[i]\n",
    "            if is_sorted(curr):\n",
    "                cur = curr\n",
    "            else:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        n = len(strs[0])\n",
    "        big = [False]*m \n",
    "        big[0] = True\n",
    "        delete_cnt = 0\n",
    "        for j in range(n):\n",
    "            flag = False\n",
    "            tmp = big[:]\n",
    "            for i in range(1,m):\n",
    "                if(strs[i-1][j] > strs[i][j]):\n",
    "                    if(big[i] == False):\n",
    "                        flag = True\n",
    "                        break\n",
    "                elif(strs[i-1][j] < strs[i][j]):\n",
    "                    big[i] = True\n",
    "            if(flag):\n",
    "                big = tmp[:]\n",
    "                delete_cnt += 1\n",
    "        return delete_cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        ans = 0\n",
    "        gt = [False] * n\n",
    "        gt[0] = True\n",
    "        for col in zip(*strs):\n",
    "            ifdel = False\n",
    "            tmp = gt.copy()\n",
    "            for i in range(1, n):\n",
    "                if gt[i]:\n",
    "                    continue\n",
    "                if col[i] < col[i-1]:\n",
    "                    ifdel = True\n",
    "                    break\n",
    "                elif col[i] > col[i-1]:\n",
    "                    tmp[i] = True\n",
    "            if ifdel:\n",
    "                ans += 1\n",
    "            else:\n",
    "                gt = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs)\n",
    "        l = len(strs[0])\n",
    "        small = [False] * (n - 1)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(l):\n",
    "            flag = False\n",
    "            for j in range(n - 1):\n",
    "                if small[j]:\n",
    "                    continue\n",
    "                if strs[j][i] > strs[j + 1][i]:\n",
    "                    flag = True\n",
    "                    break\n",
    "            \n",
    "            if flag:\n",
    "                res += 1\n",
    "            else:\n",
    "                for j in range(n - 1):\n",
    "                    if strs[j][i] < strs[j + 1][i]:\n",
    "                        small[j] = True\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        ans = 0\n",
    "        n = len(strs[0])\n",
    "        cur = [\"\"] * len(strs)\n",
    "        for i in range(n):\n",
    "            cur2 = cur[:]\n",
    "            for j in range(len(strs)):\n",
    "                cur2[j] += strs[j][i]\n",
    "            if all(cur2[k] <= cur2[k+1] for k in range(len(cur2) - 1)):\n",
    "                cur = cur2\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\r\n",
    "        res = 0 \r\n",
    "        # 检测每一组是否有序 \r\n",
    "        # 如果已经有严格降序，就不用都有序\r\n",
    "\r\n",
    "        #g[i][j] 为True表示strs[i] 严格大于 strs[j]\r\n",
    "        g = [[False] * 105 for _ in range(105) ]\r\n",
    "\r\n",
    "        n = len(strs)\r\n",
    "        for j in range(len(strs[0])):\r\n",
    "            chs = []\r\n",
    "            for s in strs:\r\n",
    "                chs.append(s[j])\r\n",
    "            flag = False \r\n",
    "            for i in range(1, len(chs)):\r\n",
    "                for k in range(i):\r\n",
    "                    if g[k][i]:continue\r\n",
    "                    if chs[k] > chs[i]:\r\n",
    "                        # 需要删除\r\n",
    "                        flag = True\r\n",
    "            if flag:\r\n",
    "                # g 关系不需要更新 \r\n",
    "                res += 1\r\n",
    "            else:\r\n",
    "                # 不需要删除，将严格大于的关系更新\r\n",
    "                for i in range(len(chs)):\r\n",
    "                    for k in range(i + 1, len(chs)):\r\n",
    "                        if chs[i] < chs[k]:\r\n",
    "                            g[i][k] = True \r\n",
    "        return res \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        cuts = [False for _ in range(len(strs) - 1)]\n",
    "        res = 0\n",
    "        for col in zip(*strs):\n",
    "            if all(cuts[i] or col[i] <= col[i + 1] for i in range(len(col) - 1)):\n",
    "                for i in range(len(col) - 1):\n",
    "                    if col[i] < col[i + 1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs[0])\n",
    "        count = 0\n",
    "        last_equal = [True] * (len(strs) - 1)\n",
    "        for j in range(n):\n",
    "            flag, temp = True, [e for e in last_equal]\n",
    "            for i in range(1, len(strs)):\n",
    "                if strs[i][j] < strs[i - 1][j] and temp[i - 1]:\n",
    "                    count += 1\n",
    "                    flag = False\n",
    "                    break\n",
    "                elif strs[i][j] == strs[i - 1][j] and temp[i - 1]:\n",
    "                    flag = False\n",
    "                elif strs[i][j] > strs[i - 1][j]:\n",
    "                    temp[i - 1] = False\n",
    "            else:\n",
    "                last_equal = temp\n",
    "            if flag:\n",
    "                return count\n",
    "       \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n=len(strs)\n",
    "        count=0\n",
    "        flag=-1\n",
    "        while flag!=0:\n",
    "            flag=0\n",
    "            for j in range(len(strs[0])):\n",
    "                if flag:break\n",
    "                pre=strs[0][:j+1]\n",
    "                for i in range(n):\n",
    "                    if flag:break\n",
    "                    if strs[i][:j+1]<pre:\n",
    "                        flag=1\n",
    "                        count+=1\n",
    "\n",
    "                        for k in range(n):\n",
    "                            strs[k]=strs[k][:j]+strs[k][j+1:]\n",
    "                    else:pre=strs[i][:j+1]\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        n = len(strs[0])\n",
    "        big = [False]*m \n",
    "        big[0] = True\n",
    "        delete_cnt = 0\n",
    "        for j in range(n):\n",
    "            flag = False\n",
    "            tmp = big[:]\n",
    "            cnt = 1\n",
    "            for i in range(1,m):\n",
    "                if(strs[i-1][j] > strs[i][j]):\n",
    "                    if(big[i] == False):\n",
    "                        flag = True\n",
    "                        break\n",
    "                    cnt += 1\n",
    "                elif(strs[i-1][j] < strs[i][j]):\n",
    "                    big[i] = True\n",
    "                    cnt += 1\n",
    "            if(flag):\n",
    "                big = tmp[:]\n",
    "                delete_cnt += 1\n",
    "            if(cnt == m):\n",
    "                return delete_cnt\n",
    "        return delete_cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m, n = len(strs), len(strs[0])\n",
    "        noCheck = set()\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            tag = False\n",
    "            insq = set()\n",
    "            for j in range(m - 1):\n",
    "                if j not in noCheck:\n",
    "                    if strs[j + 1][i] < strs[j][i]:\n",
    "                        tag = True\n",
    "                        break\n",
    "                    elif strs[j + 1][i] > strs[j][i]:\n",
    "                        insq.add(j)\n",
    "            if tag:\n",
    "                ans += 1\n",
    "            else:\n",
    "                noCheck = noCheck | insq\n",
    "                    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, A: List[str]) -> int:\n",
    "        count = 0\n",
    "        # 记录的是满足条件的所有列的每一个元素的的严格大于情况.\n",
    "        cuts = [False] * (len(A) - 1)\n",
    "        \n",
    "        for col in zip(*A):\n",
    "            \n",
    "            # sign_1表示cuts是否全都为True\n",
    "            # sign_2表示当前列是否满足条件\n",
    "            sign_1 = sign_2 = True\n",
    "            for i in range(len(col)-1):\n",
    "                if not cuts[i]:\n",
    "                    sign_1 = False\n",
    "                if not cuts[i] and col[i] > col[i+1]:\n",
    "                    sign_2 = False\n",
    "                    break\n",
    "            # 如果cuts全都是严格大于,那么就可以返回结果了.\n",
    "            if sign_1:\n",
    "                break\n",
    "            # 如果当前列不满足条件,就需要删除,否则更新cuts\n",
    "            if sign_2:\n",
    "                for i in range(len(col)-1):\n",
    "                    if col[i] < col[i+1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        def isSorted(strs):\n",
    "            return all(strs[i] <= strs[i+1] for i in range(len(strs)-1))\n",
    "\n",
    "        ans = 0\n",
    "        # cur : all rows we have written\n",
    "        curr = [''] * len(strs)\n",
    "        # unzip strs\n",
    "        for col in zip(*strs):\n",
    "            curr2 = curr[:]\n",
    "            for i, c in enumerate(col):\n",
    "                curr2[i] = curr2[i] + c\n",
    "\n",
    "            if isSorted(curr2):\n",
    "                curr = curr2\n",
    "            else:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n, m = len(strs), len(strs[0])\n",
    "        ans, st = 0, [0 for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            tmp, ok = [0 for _ in range(n)], 1\n",
    "            for j in range(1, n):\n",
    "                l1, l2 = strs[j - 1][i], strs[j][i]\n",
    "                if st[j] == 1 or l1 < l2: tmp[j] = 1\n",
    "                elif l1 > l2:\n",
    "                    ok = 0\n",
    "                    break\n",
    "            if ok == 0: ans += 1\n",
    "            else: st = tmp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n, m = len(strs), len(strs[0])\n",
    "        increasing = [False] * n\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            flag = True\n",
    "            for j in range(1, n):\n",
    "                if not increasing[j] and strs[j][i] < strs[j-1][i]:\n",
    "                    ans += 1\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                for j in range(1, n):\n",
    "                    if not increasing[j] and strs[j][i] > strs[j-1][i]:\n",
    "                        increasing[j] = True\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minDeletionSize(self, A):\n",
    "        def is_sorted(A):\n",
    "            return all(A[i] <= A[i+1] for i in range(len(A) - 1))\n",
    "        ans = 0\n",
    "        cur = [\"\"] * len(A)  \n",
    "        for col in zip(*A):\n",
    "            cur2 = cur[:]\n",
    "            for i, letter in enumerate(col):\n",
    "                cur2[i] = cur2[i] + letter\n",
    "            if is_sorted(cur2):\n",
    "                cur = cur2\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 优化贪心\n",
    "class Solution:\n",
    "    def minDeletionSize(self, A: List[str]):\n",
    "        # cuts[i] is True : we don't need to check col[i] <= col[i+1]\n",
    "        cuts = [False] * (len(A) - 1)\n",
    "\n",
    "        ans = 0\n",
    "        for col in zip(*A):\n",
    "            if all(cuts[i] or col[i] <= col[i+1] for i in range(len(col) - 1)):\n",
    "                for i in range(len(col) - 1):\n",
    "                    if col[i] < col[i+1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        n = len(strs[0])\n",
    "        big = [False]*m \n",
    "        big[0] = True\n",
    "        delete_cnt = 0\n",
    "        for j in range(n):\n",
    "            flag = False\n",
    "            tmp = big[:]\n",
    "            for i in range(1,m):\n",
    "                if(strs[i-1][j] > strs[i][j]):\n",
    "                    if(big[i] == False):\n",
    "                        flag = True\n",
    "                elif(strs[i-1][j] < strs[i][j]):\n",
    "                    big[i] = True\n",
    "            if(flag):\n",
    "                big = tmp[:]\n",
    "                delete_cnt += 1\n",
    "        return delete_cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        def is_sorted(s):\n",
    "            return all(x <= y for x, y in pairwise(s))\n",
    "        cur = [\"\"] * len(strs)\n",
    "        ans = 0\n",
    "        for col in zip(*strs):\n",
    "            cur2 = cur[:]\n",
    "            for i, letter in enumerate(col):\n",
    "                cur2[i] = cur[i] + letter\n",
    "            \n",
    "            if is_sorted(cur2):\n",
    "                cur = cur2\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minDeletionSize(self, A):\n",
    "        # cuts[i] is True : we don't need to check col[i] <= col[i+1]\n",
    "        cuts = [False] * (len(A) - 1)\n",
    "\n",
    "        ans = 0\n",
    "        for col in zip(*A):\n",
    "            if all(cuts[i] or col[i] <= col[i+1] for i in range(0, len(col) - 1, 1)):\n",
    "                for i in range(0, len(col) - 1, 1):\n",
    "                    if col[i] < col[i+1]:\n",
    "                        cuts[i] = True\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        rows = [(0, m-1)]\n",
    "        ans = 0\n",
    "        for col in zip(*strs):\n",
    "            new_rows = []\n",
    "            deleted = False\n",
    "            for start, end in rows:\n",
    "                new_start = -1\n",
    "                for i in range(start, end):\n",
    "                    if col[i] > col[i+1]:\n",
    "                        deleted = True\n",
    "                        ans += 1\n",
    "                        break\n",
    "                    elif col[i] == col[i+1]:\n",
    "                        if new_start == -1:\n",
    "                            new_start = i\n",
    "                    else:\n",
    "                        if new_start != -1:\n",
    "                            new_rows.append((new_start, i))\n",
    "                            new_start = -1\n",
    "                if new_start != -1:\n",
    "                    new_rows.append((new_start, end))\n",
    "                if deleted:\n",
    "                    break\n",
    "            if deleted:\n",
    "                continue\n",
    "            if not new_rows:\n",
    "                break\n",
    "            rows = new_rows\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        from collections import defaultdict\n",
    "        n = len(strs)\n",
    "        m = len(strs[0])\n",
    "        checked = defaultdict(int)\n",
    "        res = 0\n",
    "        for i in range(m): # each index\n",
    "            flag = 1\n",
    "            indices = []\n",
    "            # print(f'i = {i}')\n",
    "            for j in range(n-1): # each word\n",
    "                # print(f'{j}')\n",
    "                if checked[j]:\n",
    "                    # print('skipped')\n",
    "                    continue\n",
    "                if (strs[j][i]) < (strs[j+1][i]):\n",
    "                    indices.append(j)\n",
    "                if strs[j][i] > strs[j+1][i]:\n",
    "                    flag = 0\n",
    "                    res += 1\n",
    "                    # print('false')\n",
    "                    break\n",
    "            if flag:\n",
    "                for j in indices:\n",
    "                    checked[j] = 1\n",
    "                    # print('checked')\n",
    "            # print()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m=len(strs)\n",
    "        n=len(strs[0])\n",
    "        cuts=[False]*(len(strs)-1)\n",
    "        count=0\n",
    "        for col in zip(*strs):\n",
    "           # print(col)\n",
    "            sign1=True\n",
    "            sign2=True\n",
    "            for i in range(len(col)-1):\n",
    "                if not cuts[i]:\n",
    "                    sign1=False\n",
    "                if not cuts[i] and col[i]>col[i+1]:\n",
    "                    sign2=False\n",
    "                    break\n",
    "            if sign1:\n",
    "                break\n",
    "            if sign2:\n",
    "                for i in range(len(col)-1):\n",
    "                    if col[i]<col[i+1]:\n",
    "                        cuts[i]=True\n",
    "            else:\n",
    "                count+=1\n",
    "       # print(cuts)\n",
    "        return count\n",
    "   \n",
    "\n",
    "\n",
    "\n",
    "        #return n-ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        ans = [] \n",
    "        m = len(strs[0])\n",
    "        n = len(strs)\n",
    "        c = [(0, n-1)]\n",
    "        i = 0 \n",
    "        while c and i < m:\n",
    "            #print(c, i)\n",
    "            flag = 1 \n",
    "            for l, r in c:\n",
    "                for j in range(l+1,r+1):\n",
    "                    if ord(strs[j][i]) < ord(strs[j-1][i]):\n",
    "                        flag = 0 \n",
    "                        break \n",
    "            if flag == 0:\n",
    "                ans.append(i) \n",
    "            else:\n",
    "                sz = len(c) \n",
    "                #nl, nr = floag('inf'), 0 \n",
    "                for _ in range(sz):\n",
    "                    l,r = c.pop(0) \n",
    "                    nl, nr = r, l \n",
    "                    for j in range(l+1,r+1):\n",
    "                        if strs[j][i] == strs[j-1][i]:\n",
    "                            nl = min(nl, j-1)\n",
    "                            nr = j \n",
    "                        elif nr > nl:\n",
    "                            c.append((nl, nr))\n",
    "                            nl, nr = r, l \n",
    "                    if nr > nl:\n",
    "                        c.append((nl,nr)) \n",
    "            i+=1 \n",
    "            #print(c, i)\n",
    "         \n",
    "        #print(ans) \n",
    "        return len(ans) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m=len(strs)\n",
    "        n=len(strs[0])\n",
    "        cuts=[False]*(len(strs)-1)\n",
    "        count=0\n",
    "        for col in zip(*strs):\n",
    "            sign1=True\n",
    "            sign2=True\n",
    "\n",
    "            for i in range(m-1):\n",
    "                if not cuts[i]:\n",
    "                    sign1=False\n",
    "                if not cuts[i] and col[i]>col[i+1]:\n",
    "                    sign2=False\n",
    "                    break\n",
    "            if sign1:\n",
    "                break \n",
    "            if sign2:\n",
    "                for i in range(m-1):\n",
    "                    if col[i]<col[i+1]:\n",
    "                        cuts[i]=True\n",
    "            else:\n",
    "                count+=1\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        n = len(strs[0])\n",
    "\n",
    "        vis = [False] * (m-1)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            flag = True\n",
    "            for j in range(m-1):\n",
    "                if not vis[j] and strs[j][i] > strs[j+1][i]:\n",
    "                    res += 1\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                for j in range(m-1):\n",
    "                    if strs[j][i] < strs[j+1][i]:\n",
    "                        vis[j] = True\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        m = len(strs)\n",
    "        n = len(strs[0])\n",
    "        big = [False]*m \n",
    "        big[0] = True\n",
    "        delete_cnt = 0\n",
    "        for j in range(n):\n",
    "            flag = False\n",
    "            tmp = big[:]\n",
    "            for i in range(1,m):\n",
    "                if(strs[i-1][j] > strs[i][j]):\n",
    "                    if(big[i] == False):\n",
    "                        flag = True\n",
    "                        break\n",
    "                elif(strs[i-1][j] < strs[i][j]):\n",
    "                    big[i] = True\n",
    "            if(flag):\n",
    "                big = tmp[:]\n",
    "                delete_cnt += 1\n",
    "        return delete_cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        def is_sorted(x):\n",
    "            return all(x[i] <= x[i+1] for i in range(len(x)-1))\n",
    "        cur = ['']*len(strs)\n",
    "        # *strs将每一列的元素放一起\n",
    "        ans = 0\n",
    "        for col in zip(*strs):\n",
    "            cur2 = cur[:]\n",
    "            for j,c in enumerate(col):\n",
    "                cur2[j] = cur2[j]+c\n",
    "            if is_sorted(cur2):\n",
    "                cur = cur2\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "   def minDeletionSize(self, strs: List[str]) -> int:\n",
    "        n = len(strs[0])\n",
    "        m = len(strs)\n",
    "        lst = ['' for _ in range(m)]\n",
    "        for i in range(n):\n",
    "            flag = 2\n",
    "            lstNew = []\n",
    "            num = 0\n",
    "            for j in range(m):\n",
    "                s = strs[j]\n",
    "                lstNew.append(lst[j] + s[i])\n",
    "                numNow = ord(s[i])\n",
    "                if numNow > num:\n",
    "                    num = ord(s[i])\n",
    "                elif numNow == num and flag != 0:\n",
    "                    flag = 1\n",
    "                else:\n",
    "                    flag = 0\n",
    "            if flag == 0:\n",
    "                if sorted(lstNew) == lstNew:\n",
    "                    lst = lstNew\n",
    "            else:\n",
    "                lst = lstNew\n",
    "        return n - len(lst[0])\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 贪心\n",
    "class Solution:\n",
    "    def minDeletionSize(self, A: List[int]):\n",
    "        def is_sorted(A):\n",
    "            return all(A[i] <= A[i+1] for i in range(len(A) - 1))\n",
    "\n",
    "        ans = 0\n",
    "        # cur : all rows we have written\n",
    "        # For example, with A = [\"abc\",\"def\",\"ghi\"] we might have\n",
    "        # cur = [\"ab\", \"de\", \"gh\"].\n",
    "        cur = [\"\"] * len(A)  \n",
    "\n",
    "        for col in zip(*A):\n",
    "            # cur2 : What we potentially can write, including the\n",
    "            #        newest column 'col'.\n",
    "            # Eg. if cur = [\"ab\",\"de\",\"gh\"] and col = (\"c\",\"f\",\"i\"),\n",
    "            # then cur2 = [\"abc\",\"def\",\"ghi\"].\n",
    "            cur2 = cur[:]\n",
    "            for i, letter in enumerate(col):\n",
    "                cur2[i] = cur2[i] + letter\n",
    "\n",
    "            if is_sorted(cur2):\n",
    "                cur = cur2\n",
    "            else:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
